#include "stdafx.h"
#include "HeapSort.h"
///Implementation of the class

//Static method to sort an input array
void HeapSort::Sort(int nList[], int nLength){
	int tmp;
	HeapSort::BuildMaxHeap(nList, nLength);
	for(int i = nLength - 1; i > 0 ; --i)
	{
		tmp = nList[i];
		nList[i] = nList[0];
		nList[0] = tmp;
		MaxHeapify(nList, i, 0);
	}
}

void HeapSort::MaxHeapify(int nList[], int nLength, int i)
{
	int l = 2*i + 1;
	int r = 2*(i + 1);
	int max = i;

	if( l < nLength && nList[max] < nList[l])
	{
		max = l;
	}

	if( r < nLength && nList[max] < nList[r])
	{
		max = r;
	}

	if(max != i)
	{
		int tmp = nList[i];
		nList[i] = nList[max];
		nList[max] = tmp;
		MaxHeapify(nList, nLength, max);
	}
}

void HeapSort::BuildMaxHeap(int nList[], int nHeapSize)
{
	for(int i = nHeapSize/2 - 1; i >= 0; --i)
	{
		MaxHeapify(nList, nHeapSize, i);
	}
}
